package com.major.dawn.leetCode.tree;

import java.util.LinkedList;
import java.util.List;

public class Solution {


    public List<Integer> preorderTraversal(TreeNode root) {

        List<Integer> outPut = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();

        stack.add(root);

        while (stack.size() != 0) {
            TreeNode first = stack.getFirst();
            outPut.add(first.val);
            stack.remove();
            if (first.right != null) {
                stack.add(first.right);
            }
            if (first.left != null) {
                stack.addFirst(first.left);
            }

        }


        return outPut;
    }

    public List<Integer> preorderTraversalByRecusion(TreeNode root) {
        List<Integer> outPut = new LinkedList<>();
        if (root == null) {
            return outPut;
        }
        readTreeNode(root, outPut);

        return outPut;
    }

    public void readTreeNode(TreeNode root, List<Integer> outPut) {
        if (root == null) {
            return;
        }
        outPut.add(root.val);
        readTreeNode(root.left, outPut);
        readTreeNode(root.right, outPut);

    }

    public List<Integer> inorderTraversal(TreeNode root) {

        List<Integer> outPut = new LinkedList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);
        TreeNode curr = root;
        while (curr != null || (!stack.isEmpty() && stack.getFirst() != null)) {

            while (curr != null) {
                stack.add(curr);
                curr = curr.left;
            }
            curr = stack.getFirst();
            stack.remove();
            outPut.add(curr.val);
            curr = curr.right;
        }

        return outPut;
    }

    public String addStrings(String num1, String num2) {
        if (num1 == null && num1.equals("")) {
            return num2;
        }
        if (num2 == null && num2.equals("")) {
            return num1;
        }
        char[] chars1 = num1.toCharArray();
        char[] chars2 = num2.toCharArray();
        int chars1Index = chars1.length -1 ;
        int chars2Index = chars2.length -1 ;

        int addBit = 0;
        char[] target;
        int targetIndex;


        if (chars1Index > chars2Index) {
            target = chars1;
            targetIndex = chars1Index;

        }else {
            target = chars2;
            targetIndex = chars1Index;

        }

        while (chars1Index > -1 && chars2Index > -1) {
            char tem = (char) (chars1[chars1Index] + chars2[chars2Index] - 48 + addBit);
            addBit = 0;
            if (tem > 57) {
                tem = (char) (tem - 10);
                addBit = 1;
            }
            target[targetIndex] = tem;
            chars1Index--;
            chars2Index--;
            targetIndex--;
        }


        while (addBit == 1 && targetIndex > -1) {
            char tem = (char) (target[targetIndex] + addBit);
            addBit = 0;
            if (tem > 57) {
                tem = (char) (tem - 10);
                addBit = 1;
            }
            target[targetIndex] = tem;
            targetIndex--;
        }

        if (addBit == 1) {
            char[] temChars = new char[target.length + 1];
            System.arraycopy(target, 0, temChars, 1, target.length);
            temChars[0] = '1';
            return String.valueOf(temChars);
        }

        return String.valueOf(target);




    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.addStrings("9", "99");
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {

        return false;
    }


}



